1 文件系统概述
为什么引入文件系统
长期保存（大量的）数据
方便用户使用
文件是有名字的记录在外存中的一组有逻辑意义的数据项序列
什么是文件系统
文件系统是OS中用来管理文件的那一部分软件
文件系统功能
统一管理文件的存储空间，实施存储空间的分配与回收
实现文件信息的共享，提供文件的保护和保密措施
实现文件的按名访问
访问的透明性：用户不关心文件的物理位置和存储结构
向用户提供一个方便使用的接口，提供对文件系统操作的命令
提供与I/O的统一接口
文件分类：
Unix系统将文件分为3类:
普通文件(regular)：ASCII或二进制文件
目录文件(directory)
特殊文件：设备文件，管道，套接字（socket），符号链接等
2 文件的结构与存取方式
文件是存在磁盘上的
2.1 磁盘
磁盘有扇片 磁道 扇区
扇区——磁盘最小可寻址单元
簇——存储块，固定数量的扇区
- 平均存取时间
T=平均寻道时间+平均旋转等待时间+数据传输时间（有时候忽略不计）
其中
平均寻道时间——磁头寻找到指定磁道所需要的平均时间（大约5ms）
平均旋转等待时间——指定扇区旋转到磁头下方所需要的平均时间（约4-6ms）
- 磁盘响应时间=平均存取时间+排队时间+控制器时间
注意想明白这里的0.5的来源
2.2 文件的物理结构
2.2.1 连续结构
文件的数据存放在若干连续的物理块中
优点：
简单，只要记住首块的地址和文件长度即可
支持顺序存取和随机存取
顺序存取速度快
所需的磁盘寻道时间最少
缺点：
不利于文件的动态增长
若预留空间：浪费，而且预先不知道文件的最大长度
否则需要重新分配和移动
不利于文件内容的插入和删除
存在外部碎片问题
2.2.2 链式结构
一个文件的数据存放在若干不连续的物理块中，各块之间通过指针连接，
每个物理块指向下一个物理块
优点
提高了磁盘空间利用率
不存在外部碎片问题
有利于文件的插入和删除
有利于文件的动态扩充
缺点：
随机存取相当缓慢
需要更多的寻道时间
链接指针占用一定的空间
改进变形
FAT表
文件分配表FAT的一种实现：
磁盘的每个分区包含一个FAT，分区中的每个盘块在其中占有1项（以块号为索引），指出文件中下一块的块号。
在目录项中包含文件首块的块号。
2.2.3 索引结构
一个文件的数据存放在若干不连续的物理块中，系统为每个文件建立一个专用数据结构–索引表。
索引表存放逻辑块号与物理块号的对应关系
一个索引表就是磁盘块地址（块号）数组，其中第i个条目存放的是逻辑块号i对应的物理块号
文件目录的目录项中指出索引表的物理地址
优点：保持了链接结构的优点，又避免了其缺点
既能顺序存取，又能随机存取
能满足文件动态增长、插入、删除的要求
能充分利用外存空间
缺点：
索引表本身带来了系统开销
UNIX文件系统采用的是多级混合索引结构。
每个文件的索引表为13个索引项
最前面10项直接登记存放文件数据的物理块号（直接寻址）
如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址
UNIX中采用了三级索引结构后，文件最大可达16M个物理块
索引表的组织方式
如果文件很大，索引表较大，超过了一个物理块，就必须考虑索引表的组织方式，即怎么去存储索引表
索引表的组织方式:
（1）连续方式
索引表占用多个连续的盘块
（2）链接方式
索引表按照链式结构组织，占用多个不连续的盘块
（3）多级索引（多重索引）
例如，二级索引：将一个大文件的所有索引表（二级索引）的地址放在另一个索引表（一级索引）中
此外，还有三级索引等。
题目
设每个盘块4kB，每个盘块号4B，则采用3次间址可表示的文件最大长度为 [4T] B。
2.3 文件的存取方式
主要有顺序存取和随机存取两种。
1 顺序存取
对文件中的数据按逻辑顺序进行读/写的存取方式
2 随机存取
对文件中的数据按任意顺序进行读/写的存取方式
3 按键（key）存取：如DBMS
还与介质有关
3 文件目录
3.1 基本概念
几个基本的概念
1 文件控制块
文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有相关信息（文件属性）
基本信息：文件的名字、地址（起始物理块号）、长度、结构（逻辑结构、物理结构）、类型
存取控制信息：文件属主（owner）、存取权限或口令
使用信息：共享计数，文件的建立、修改日期等
2 文件目录
把所有的FCB组织在一起，就构成了文件目录
即文件控制块的有序集合
3 目录项
构成文件目录的项目（目录项就是FCB）
4 目录文件
为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，
这个文件就叫目录文件
目录主要是为了系统快速实现“按名访问”而引入的，
查目录是文件系统最频繁的操作，因此目录的合理组织很重要
3.2 目录结构
单级目录结构
为所有文件建立一个目录文件（组成一线性表）
优点：简单，易实现
缺点：
限制了用户对文件的命名（容易出现“命名冲突”）
顺序检索文件时，平均检索时间长
不利于对文件的共享
多级目录结构
对二级目录简单扩充可得三级或三级以上的多级目录结构，
即允许每一级目录中的FCB要么指向文件，要么指向下一级子目录。
这是当今主流OS普遍采用的目录结构
优点：
层次结构清晰，便于管理和保护；有利于文件分类；
能较好地避免重名问题；提高了文件检索速度；有利于访问权限的控制
3.3 文件目录检索
访问文件时，必须首先确定读写文件的地址，需要下列2步：
（1）目录检索：根据文件名，查目录，确定文件的起始地址。
（2）文件寻址：确定所要访问文件内容的起始位置（地址）。
3.3.1 目录检索
文件的“按名存取”是通过查目录实现的，系统按照文件的路径名检索
基本的目录检索技术主要有：
线性检索法
Hash方法
为了加快目录检索，许多系统引入当前目录（工作目录）、相对路径名等。
文件寻址
根据目录项（FCB）中记录的文件物理地址等信息，
求出文件的任意记录或字节在存取介质上的地址
文件寻址与文件的物理结构和逻辑结构以及设备的物理特性有关
文件的内容是以块为单位存储的。
但存取文件时，对于记录式文件，是以逻辑记录为单位提出存取要求的，因此，
存储介质上的物理块长度与逻辑记录的长度是否匹配直接影响到对文件的寻址
3.4 文件目录的实现
当查找文件时候，需要依次将存放目录的物理块装入内存，逐一比较文件名，直到找到为止
例如：文件说明占128B，每块512B，则每块可存放4个目录项
设目录文件占用的盘块数是N个，则要找到一个目录项，
平均需要读入多少个盘块？(N+1)/2块
把文件说明信息（FCB）都放在目录项中的缺点：
查找文件缓慢，因为目录项较大
文件目录平常放在外存中，当文件很多时，可能占用大量的外存物理块
但实际上我们文件检索只需要文件名，不需要那么多其他的信息
所以我们将文件说明分成两部分 把FCB分成两部分
1 符号目录项——包括文件名，文件号
2 基本目录项——除文件名以外的所有信息
目录项分解法的典型实现
1 符号文件目录+基本文件目录
2 目录项 +I 节点
Unix/Linux采用此方法，它把符号目录项称为目录项，而把基本目录项称为I节点（Index node，索引节点），这样，目录项中的文件号就是I节点号。
举例一个查找过程
一个文件存在根目录下的wang目录下，若获得这个文件的I结点号，需要读几个磁盘物理块
注意 I节点只存储当前目录或者文件的信息！！！
I节点存的物理块号（如果是目录的话，就是目录项的地址，如果是文件的话，则是文件的首地址）！！！
首先根据根目录的I节点号以及内存中的I节点与物理块号的对应关系，可以知道根目录I节点的地址，去读这个地址的内容（第一次读物理块读取），即是获得了根目录的目录项的地址，去读根目录的目录项（第二次物理块读取）可以知道wang对应的I节点物理地址，读wang的I节点地址内容（第三次读取）可以知道wang的目录项地址，读wang目录项地址就可以获得文件a.c的I节点号（第四次读取）
如果是索引的话 获得的地址不是物理块地址，而是索引表地址，所以需要每一个获取地址都增加一次，总共六次
4 空闲存储空间的管理
4.1 空闲区表
将所有空闲区记录在一个表中。
适合连续文件的外存分配与回收。如今很少用
4.2 空闲块链
把所有空闲块链成一个链，适合离散分配
扩展：
①不断地适度增加块大小
从最早的512B 1KB 2KB 4KB 8KB 16KB 32KB 64KB。
②成组链接法
链上每个节点记录1组空闲块。适合大型文件系统，分配、释放快，
链占用空间少（除首组外均隐藏在空闲块中）。UNIX用之
成组连接法
4.3 位图
用一串二进制位反映磁盘空间的分配情况，每个物理块对应1位，已分配的物理块为1，否则为0
申请物理块时，可以在位图中查找为0的位，返回对应的物理块号
归还时，将对应位设置为0
描述能力强，适合各种物理结构
5 文件的使用
为方便用户使用文件，文件系统提供对文件的各种操作，
使用的形式包括系统调用或命令
① 提供设置和修改用户对文件访问权限的操作
② 提供建立、修改、删除目录的操作
③ 提供文件共享、设置访问路径的操作
④ 提供创建、打开、读、写、关闭、删除文件等操作
其中，最基本的操作是：打开、关闭、读、写文件等
为什么要 打开/关闭文件呢
open：把文件说明信息（FCB）装入内存，便于以后的快速访问。
（1）根据指定的文件路径名，查目录，找到相应文件的目录项，检查权限；
（2）将文件说明信息装入内存；
（3）分配一个文件id（整数）。后面通过该id实施对该文件的操作。
close：
（1）释放文件说明信息所占的内存空间；
（2）把文件缓冲区中已修改的内容写回文件。
很多系统限制进程打开文件的个数，用户尽可能要关闭不再使用的文件。
打开文件会在内存建立文件的描述信息，记录文件的当前指针，有助于提高文件的访问速度与灵活性。
关闭会释放文件缓冲区，将已修改的内容写盘，释放文件描述信息所占的内存空间。若不关闭文件，则内存空间被浪费，甚至可能会使修改的内容丢失。
6 文件共享
文件共享：一个文件被多个用户或进程使用
共享的目的：
节省时间和存储空间，减少用户工作量
进程间通过文件交换信息
6.1 普通的文件共享方法
6.1.1 按路径名访问共享文件
实现简单，不需要建立另外的目录项
但路径名可能长，检索较慢
6.1.2 链接法
在相应目录项之间建立链接。即一个目录项中含有指向另一个目录项的指针。
实现方法：
在目录项中设置一个“链接属性”，
表示目录项中的“物理地址”是指向另一目录项的指针。
同时，在共享文件的目录项中包含“用户计数”。
6.1.3 基本文件目录BFD
整个文件系统有1个基本文件目录BFD：
每个文件（及目录）有1个目录项，包含系统赋予的唯一标识符ID（整数）
以及其他的文件说明信息
每个目录有1个符号文件目录SFD：除了ID = 0，1，2外,
每个目录项仅包含文件名和ID
系统把ID = 0，1，2的目录项分别作为BFD、FFD、MFD的标识符
共享方法：
若一个用户想共享另一用户的文件，只需在自己的目录文件中增加一个目录项，填上自己起的文件名和该共享文件的唯一ID即可。如ID = 6的文件。
6.2 基于I节点的文件共享方法（Unix采用）
6.2.1 硬链接
6.2.3 符号链接
在Windows中叫做 快捷方式
7 文件保护
主要涉及文件存取控制
存取控制矩阵
给出每个用户对每个文件的访问权限。
一维是所有用户，另一维是所有文件，
对应的矩阵元素是用户对文件的访问权限。
例如，访问操作分为：
读操作（r）
写操作（w）
执行操作（x）
不能执行任何操作（-）
当用户和文件较多时，很庞大。存取控制表（Access Control List，ACL）
每个文件一张ACL，将用户分类，规定每类用户的访问权限。
例如，Unix/Linux将用户分类为：
文件主（owner）
文件主的同组用户（group）
其他用户（other）存取权限表（Capability List，CL）
每个用户一张CL，规定对每个文件的访问权限。口令
用户创建文件时，设置一个口令，放在文件目录中。密码
写入时加密，读出时解密。
假定两个用户共享一个文件系统，用户A有文件a，b，e，f ，用户B有文件c，d，e，f。用户A的b和用户B的d是同一个文件。用户A的e和用户B的e不是同一个文件，用户A的f和用户B的f是同一个文件。拟定一个文件组织方案，使得A，B两个用户能够共享该文件系统而不会造成混乱
答
为了确保用户A和用户B能够共享文件系统而不会造成混乱，可以采用以下文件组织方案：
- 首先创建两个用户目录：为每个用户创建一个独立的目录，目录A和目录B。这样，用户A和用户B的文件可以分别存储在各自的目录中，避免混淆，对于用户A的e和用户B的e不是同一个文件，则可以将它们分别存放在各自的目录中，因为它们不需要共享
- 共享文件存放目录：对于文件f，创建一个共享文件存放目录，这确保了用户A和用户B可以共同访问和修改这些共享文件。
- 建立符号链接：对于用户A的b和用户B的d是同一个文件，则可以在用户A的目录中创建一个符号链接，指向用户B的文件d。这样，用户A可以访问和操作这个文件，同时避免重复存储。
通过以上的文件组织方案，用户A和用户B可以共享文件系统，各自管理自己的文件，并且能够访问和修改共享文件，同时避免重名文件和混淆。这样可以确保文件系统的整体有序性和可维护性。
已知某文件系统采用多级目录结构，逻辑块和物理块大小均为1KB，目录当做文件，采用目录项+I结点的方式。假定要读取文件/a/b/c.dat的第10600-10900个字节，针对连续结构，基本链式结构，FAT和单级索引结构这四种情况，回答下列问题
1 给出读盘过程
2 给出读盘次数（如果有必要，可以对本题未给出的条件做出合理假设）
- 读盘过程：
连续结构：根据文件/a/b/c.dat在目录中的信息，找到其起始逻辑块号。然后根据逻辑块号和文件系统的块映射关系，直接读取对应的物理块
基本链式结构：根据文件/a/b/c.dat在目录中的信息，找到对应的I节点编号。从I节点中读取文件的索引结构，逐级跳转到链式结构中的下一个块，直到找到包含所需字节范围的块。然后从该块中读取所需字节。
FAT（文件分配表）结构：根据文件/a/b/c.dat在目录中的信息，找到对应的I节点编号。从I节点中读取文件的索引结构，根据FAT表的信息，依次读取块链中的物理块，直到找到包含所需字节范围的块。然后从该块中读取所需字节。
单级索引结构：根据文件/a/b/c.dat在目录中的信息，找到对应的I节点编号。从I节点中读取文件的索引结构，根据单级索引指向的块，再根据块内的索引信息找到包含所需字节范围的块。然后从该块中读取所需字节。
- 读盘次数：
连续结构：只需进行一次读取，因为连续结构中的数据是连续存储的。
基本链式结构：根据所需字节范围的位置，可能需要多次读取。每次读取都需要跳转到下一个块。
FAT结构：根据所需字节范围的位置，可能需要多次读取。每次读取都需要根据FAT表的信息找到下一个块。
单级索引结构：根据所需字节范围的位置，可能需要多次读取。每次读取都需要根据索引结构中的信息找到下一个块。
需要注意的是，以上的读盘次数可能还会受到文件系统的缓存策略等因素的影响，这里只是基于给出的情况做出的合理估计。
为某一个应用场景设计一个文件系统，所设计的文件系统不能建立在已有的文件系统的基础上。具体要求如下：
1 举一个应用场景的例子，说明该场景下对文件系统的具体需求
2 针对具体需求给出一种文件系统的设计方案
3 对你的设计方案进行评价
应用场景示例：智慧农业控制嵌入式系统。在智慧农业系统中，用户可以通过手机或者智能音箱等设备来控制农场中的各种设备，如灯光、温度、安防等。在这个场景中，文件系统被用于存储和管理各类设备的配置文件、日志文件等数据。
文件系统设计方案：
考虑到智慧农业控制嵌入式系统的特点和需求，可以设计一种轻量级的文件系统，具备以下特点：
- 简单快速: 提供简洁的操作界面和易于理解的文件组织方式，方便用户进行文件的存储、查找和管理。优化文件系统的读写性能，以满足实时控制的需求。采用文件缓存、文件索引等技术来提升文件读写效率。
- 可靠性: 采用数据冗余和文件系统日志等机制来保证数据的完整性和可靠性，防止数据丢失或损坏。
- 安全性: 对于敏感信息，采用加密算法进行数据保护，防止数据泄露和非法访问。
- 灵活扩展: 设计分级的结构设计，以便未来能够支持新的设备类型、新的功能和协议。
- 设计方案评价：
该设计方案针对智慧农业控制嵌入式系统的需求进行了考虑，并且具备一定的可行性和可实现性。然而，对于一个完整的文件系统来说，还需要更多的细节和技术实现方面的考虑，如并发访问的处理、容错和恢复机制等。此外，还需要考虑与其他系统组件的协同工作，以确保整个智慧农业控制嵌入式系统的稳定运行和良好的用户体验
